static vector<vector<int>> nextP = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        if (grid.empty()) return 0;
        // 1、获取新鲜橘子和腐烂橘子位置
        int m = grid.size(), n = grid[0].size();
        queue<pair<int, int>> que;

        int orange_num = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 || grid[i][j] == 2) {
                    orange_num++;
                    if (grid[i][j] == 2) que.push(make_pair(i, j));
                }
            }
        }

        int bad_orange_num = que.size();

        // 2、不断循环
        int result = 0;
        while (!que.empty()) {
            int count = que.size();
            int new_bad = 0;
            for (int i = 0; i < count; i++) {
                pair<int,int> ele = que.front();
                que.pop();
                int x = ele.first;
                int y = ele.second;
                for (int i = 0; i < nextP.size(); i++) {
                    int newX = x + nextP[i][0];
                    int newY = y + nextP[i][1];
                    if (newX < 0 || newX >= m || newY < 0 || newY >= n) continue;
                    if (grid[newX][newY] == 1) {
                        new_bad++;
                        grid[newX][newY] = 2;
                        cout << newX << ":" << newY << endl;
                        bad_orange_num++;
                        que.push({newX, newY});
                    }
                }
            }
            if (new_bad) {
                result++;
            }
        }
        if (bad_orange_num == orange_num) return result;
        return -1;
    }
};
